#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#
# Copyright © 2018 crane <crane@crane-pc>
#
# Distributed under terms of the MIT license.

"""

"""


class ListNode(object):
    def __init__(self, val, next=None):
        self.val = val
        self.next = next


class Solution:
    def partition(self, head, x):
        dummy_less  = less_tail  = ListNode('dummy', None)
        dummy_great = great_tail = ListNode('dummy', None)

        node = head

        while node:
            save_next = node.next
            if node.val < x:
                less_tail.next = node
                less_tail = node
                less_tail.next = None
            else:
                great_tail.next = node
                great_tail = node
                great_tail.next = None

            # drive loop go
            node = save_next

        less_tail.next = dummy_great.next

        return dummy_less.next


def main():
    print("start main")

if __name__ == "__main__":
    main()
